package leetcode.editor.vscdev.hot100;
import leetcode.editor.utils.*;

public class lc92_reverseBetween {
    // 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
    // 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
}

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode pre = dummy;// 指向left前一个节点
        ListNode end = dummy;// 指向right对应的节点
        while ((--left)>0) {
            pre = pre.next;
        }
        while ((right--) > 0) {
            end = end.next;
        }
        ListNode next = end.next;
        end.next = null;
        reverse(pre.next);
        pre.next.next = next;// pre.next原本指向反转链表的头, 反转后则是尾部, 此处让尾部与原链表重新连接
        pre.next = end;// end为反转后链表的头
        return dummy.next;
    }

    private ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}